1. Field of the Invention
The present invention relates generally to packet forwarding engines used in telecommunications, and, in particular, to router algorithms and architectures for supporting packet filter operations with reduced memory.
2. Description of the Related Art
Packet-based communication networks, such as the Internet, typically employ a known protocol over paths or links through the network. Commonly known protocols are, for example, Transmission Control Protocol/Internet Protocol (TCP/IP) or Reservation Set-up Protocol (RSVP). Routers provided in a communication network provide a packet forwarding function whereby input data, usually in the form of one or more data packets, is switched or routed to a further destination along a network link. FIG. 1 shows a typical form of a data packet 20, which may be of variable length. Data packet 20 comprises, for example, a header 125 and payload data 150. Header 125 contains fields or parameters, such as a source address 130 where said data originate and one or more destination addresses 135 where the data is to be routed. Typically, a data packet 20 contains a single destination address. Another parameter in the header 125 may be a protocol type 140 identifying a particular protocol, such as TCP, employed in the communication network.
FIG. 2 shows a router 245 of a network node receiving streams or flows of data packets from input links 247 and routing these packet streams or flows to output links 260. To perform a forwarding function, router 245 receives a data packet at an input link 247 and a control mechanism 250 within the router utilizes an independently generated look-up table (not shown) to determine to which output link 260 the packet should be routed. It is understood that the packet may first be queued in buffers 252 before being routed, and that the forwarding function is desirably performed at a high rate for high forwarding throughput.
Source and destination addresses may indicate end hosts (not shown). Thus, data packet 20 of FIG. 1 may further comprise unique source port numbers 137 and destination port numbers 139. Header 125 may also include, for example, certain types of flags (not shown), depending upon the receiver or transmitter application.
Network service providers, while using a shared backbone infrastructure, may provide different services to different customers based on different requirements. Such requirements may be: different service pricing, security, or Quality of Service (QoS). To provide these differentiated services, routers typically include a mechanism for 1) classifying and/or isolating traffic, or packet flows, from different customers, 2) preventing unauthorized users from accessing specific parts of the network, and 3) providing customized performance and bandwidth in accordance with customer expectations and pricing.
Consequently, in addition to the packet forwarding function, router 245 of FIG. 2 may perform a packet filtering function. Packet filtering may be employed, for example, as "firewall protection" to prevent data or other information from being routed to certain specified destinations within the network. To perform packet filtering, the router 245 may be provided with a table or list of filter rules specifying routing of packets. For example, packets sent from one or more of specified sources may be denied or specific action may be taken for those packets having a specified source address. This packet filtering may be employed for layer four switching applications.
Specifically, packet filtering parses fields from the packet header 125 including, for example, both the source and destination addresses. Parsing allows each incoming packet to be classified using filter rules defined by network management software, routing protocols, or real-time reservation protocols such as RSVP.
Filter rules may also specify, for example, that received packets with fields specifying that a particular destination address should or should not be forwarded through specific output links, or that some other specific action should be taken before routing such received packets. Thus, a variety of filter rules may be implemented based on packet field information. For example, such filter rules might be based on 1) source addresses; 2) destination addresses; 3) source ports; 4) destination ports; and/or 5) any combination of these fields.
Packet filtering of the prior art generally requires either an exact match operation of the fields or a match operation defined in terms of field ranges for a filter rule. Field ranges may specify, for example, ranges of source addresses, destination addresses, source/destination port numbers, and/or protocol types. Filter rules are then applied to every packet that the router receives; that is, for each packet received by the router, every filter rule is successively applied to each packet to ascertain whether that packet is to be forwarded, restricted, or re-routed according to the filter rule. However, implementation of a large number of filter rules in a router (e.g. 500 or more) is time consuming since all filter rules must be tested. Hence, routers implementing filters having a large number of filter rules have decreased throughput, compromising a quality of service (QoS). Thus, for a router such as router 245 to maintain a relatively high level of throughput, the filtering function must be performed at very high rate with no queuing before field processing.
The IP packet header fields may each contain up to 128 bits of parameter information, including source and destination addresses, physical source and destination port numbers, interface number, protocol type, etc. Each of the fields or parameters in the header may be represented as being along an axis of a dimension. The general packet classification problem of a packet filter may then be modeled as a point-location in a multi-dimensional space. One or more field values of a packet defines a point in the multi-dimensional space. A packet filter rule associated with a range of values of each defines an object in the multi-dimensional space.
A point-location algorithm in a multi-dimensional space including multi-dimensional objects finds the object that a particular point belongs to. In other words, given a received point E.sub.j ={E.sub.1, E.sub.2, . . . E.sub.D } in a space having D dimensions, find one or more of a set of n D-dimensional objects including the point (n being an integer greater then 0). The general case of D&gt;3 dimensions may be considered for the problem of packet classification. As is known in the art the best algorithms optimized with respect to time or space have either an O(log .sup.D-1 n) time complexity with O(n) space or an O(log n) time complexity with O(n.sup.D) space. Here, O(.cndot.) mathematically represents "on the order of." Comparing algorithms on the basis of the order of operations is particularly useful since operations may be related to memory requirements (space) and execution time (time complexity).
Though algorithms with these complexity bounds are useful in many applications, they are not currently useful for packet filtering. First, packet filtering must complete within a specified amount of time, which generally forces n to be relatively small relative to asymptotic bounds, but routers must filter packets with a number of filter rules in the range of a few thousand to tens of thousands. Consequently, even point-location algorithms with poly-logarithmic time bounds are not practical for use in a high-speed router.
For example, router 245 may desirably processes n=1K filter rules of D=5 dimensions within 1 .mu.s to sustain a 1 million-packets-per-second throughput. However, an algorithm employed with O(log .sup.D-1 n) complexity and O(n) space has a log.sup.4 1024 execution time and O(1024) space, which requires 10K memory accesses (look-ups) per packet. If an O(log n) time O(n.sup.4) space algorithm is employed, then the space requirement becomes prohibitively large ( greater than 1000 Gigabytes).
For the special case of two dimensions, the filter rules defined for field ranges are modeled as objects in two dimensions, for example, forming rectangles in the 2-dimensional space. For a 2-dimensional space having non-overlapping rectangles, some packet filter algorithms have logarithmic complexity and near-linear space complexity. However, these algorithms do not consider the special problem of arbitrary overlapping rectangles in the multi-dimensional space, which requires a decision of which overlapping filter rules to apply to a packet. The problem may be resolved through a priority of the longest field prefix. An algorithm of the prior art where the time complexity is O(log log N) is based on stratified tree searches in a finite space of discrete values. Examples of these algorithms are discussed in, for example, M. De Berg, M. van Kreveld, and J. Snoeyink, Two- and Three-dimensional Point Location in Rectangular Subdivisions, Journal of Algorithms, 18:256-277, 1995. Data structures employed by this prior art algorithm require a perfect hashing operation in every level of the tree. The pre-processing complexity, without using a randomized algorithm, of calculating the perfect hash is O(min(hV,n.sup.3), where h is the number of hash functions that must be calculated and V is the size of the space. Consequently, for a 2-dimensional space, longest-prefix lookups may result in executions requiring 2.sup.32 cycles, even for a relatively small number of filter rules, even if pre-processing is only required once every several seconds.